Travelling Salesperson Problem is an example of -

ট্রাভেলিং সেলসপার্সন প্রবলেম (Travelling Salesperson Problem - TSP) কম্পিউটার বিজ্ঞানের একটি ক্লাসিক অপটিমাইজেশন সমস্যা, যেখানে একজন সেলসপার্সন বিভিন্ন শহর ঘুরে প্রতি শহর একবার করে পরিদর্শন করে আবার শুরুর শহরে ফিরে আসবে, এবং এর মধ্যে সবচেয়ে ছোট পথটি খুঁজে বের করতে হবে। এটি কম্পিউটেশনাল কমপ্লেক্সিটি থিওরির একটি গুরুত্বপূর্ণ উদাহরণ।

TSP সাধারণত NP-Hard শ্রেণীর একটি সমস্যা। আসুন, এই শ্রেণীগুলো সম্পর্কে সংক্ষেপে জেনে নিই:

    
• পলিনোমিয়াল-টাইম (Polynomial-time): এই শ্রেণীর সমস্যাগুলো P (Polynomial) শ্রেণীর অন্তর্ভুক্ত। P শ্রেণীর সমস্যাগুলো এমন যে, তাদের সমাধান পলিনোমিয়াল সময়ে খুঁজে বের করা যায় (যেমন \(O(n^k)\) যেখানে \(n\) হলো ইনপুটের আকার এবং \(k\) একটি ধ্রুবক)। ট্রাভেলিং সেলসপার্সন প্রবলেম এই শ্রেণীর অন্তর্ভুক্ত নয়, কারণ এর সমাধান খুঁজে বের করতে সাধারণত এক্সপোনেনশিয়াল সময় লাগে বলে ধারণা করা হয়।
    
• NP (Non-deterministic Polynomial-time): NP শ্রেণীর সমস্যাগুলো এমন যে, তাদের জন্য একটি প্রদত্ত সমাধান সঠিক কিনা তা পলিনোমিয়াল সময়ে যাচাই (verify) করা যায়। TSP-এর ডিসিশন ভার্সন (যেমন: একটি নির্দিষ্ট দূরত্ব K-এর মধ্যে কোনো পথ আছে কিনা?) NP শ্রেণীর অন্তর্ভুক্ত, কারণ একটি প্রস্তাবিত পথ দেওয়া হলে তা সহজেই পরীক্ষা করা যায় যে এর দৈর্ঘ্য K-এর চেয়ে কম বা সমান কিনা।
    
• NP-Complete (Non-deterministic Polynomial-time Complete): NP-Complete সমস্যাগুলো NP এবং NP-Hard উভয় শ্রেণীর অন্তর্ভুক্ত। অর্থাৎ, একটি NP-Complete সমস্যাকে পলিনোমিয়াল সময়ে ভেরিফাই করা যায় এবং NP-তে থাকা যেকোনো সমস্যাকে পলিনোমিয়াল সময়ে এই NP-Complete সমস্যায় রূপান্তর করা যায়। ট্রাভেলিং সেলসপার্সন প্রবলেম এর ডিসিশন ভার্সন (Decision TSP) একটি NP-Complete সমস্যা।
    
• NP-Hard (Non-deterministic Polynomial-time Hard): NP-Hard সমস্যা হলো এমন এক শ্রেণীর সমস্যা যা কমপক্ষে NP-Complete সমস্যাগুলোর মতোই কঠিন। একটি সমস্যাকে NP-Hard বলা হয় যদি NP-তে থাকা যেকোনো সমস্যার উদাহরণকে পলিনোমিয়াল সময়ে ওই সমস্যার উদাহরণে রূপান্তর করা যায়। সাধারণত, অপটিমাইজেশন সমস্যাগুলো (যেমন: সর্বনিম্ন দূরত্ব খুঁজে বের করা) NP-Hard হয়। ট্রাভেলিং সেলসপার্সন প্রবলেম-এর অপটিমাইজেশন সংস্করণ (সর্বনিম্ন দূরত্বের পথ খুঁজে বের করা) একটি ক্লাসিক NP-Hard সমস্যা।

যেহেতু NP-Complete সমস্যাগুলো NP-Hard-এর একটি উপসেট, এবং TSP-এর অপটিমাইজেশন ফর্ম সরাসরি NP-Hard শ্রেণীভুক্ত, তাই 'NP-Hard' হলো ট্রাভেলিং সেলসপার্সন প্রবলেমের একটি সঠিক এবং ব্যাপকতর বর্ণনা।